package Datas_Structure.Tree;

/**
 * 平衡二叉树
 * 左子树和右子树的高度差绝对值小于1
 * 左右的子树也满足平衡二叉树
 * 单旋转    左旋转     右旋转
 * 双旋转：  先左再右    先右再左
 *-------------------------------------------------
 * B树中所有的叶子节点都在同一层
 * 2-3树和2-3-4树是B树的特例
 * 有两个节点的节点叫二节点，二节点要么右两个节点，要么没有节点
 * 右三个节点的节点叫三节点，三节点要么有三个节点，要么没有节点
 * B树的阶
 * 2-3树3阶的B树
 * 2-3-4树是4阶的B树
 * B+树
 * 非叶子节点只存储索引信息，不存储数据
 * 叶子节点最右边的指针指向下一个相邻的叶子节点
 * 所有的叶子节点组成了一个有序的链表
 * -------------------------------------------------
 * 哈希表（散列表）
 *   散列函数：
 *   1.直接定址法 2.数字分析法 3.平方取中法 4.取余法 5.随机数法
 *   散列函数的冲突处理
 *   1.开放地址法（1.线性探测法2.二次探测法3.在哈希法）
 *   2.链地址法
 * -------------------------------------------------
 * 图的遍历
 * 深度优先    类似于 先序遍历
 * 广度优先    类似于 层次遍历
 */
public class AvgBinaryTree {
    Node01 root;

    public void add(Node01 node) {
        //如果是一棵空树
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    /**
     * 中序遍历
     */
    public void midShow() {
        if (root != null) {
            root.midShow(root);
        }
    }
    /**
     * 查找一个节点
     */
    public Node01 search(int value){
        if (root == null){
            return null;
        }else {
            return root.search(value);
        }
    }

}

/**
 * 节点
 */
class Node01 {
    int value;
    Node01 Rnode;
    Node01 Lnode;

    public Node01(int value) {
        this.value = value;
    }
    //判断左子树的高度
    public int Rhight(){
        if (Rnode == null){
            return 0;
        }
        return Rnode.height();
    }
    //判断右子树的高度
    public int Lhight(){
        if (Lnode == null){
            return 0;
        }
        return Lnode.height();
    }
    //返回当前节点的高度
    public int height(){
        return (Math.max(Lnode==null?0:Lnode.height(),Rnode==null?0:Rnode.height()) + 1);
    }
    /**
     * 向子树中添加节点
     */
    public void add(Node01 node) {
        if (node == null) {
            return;
        }
        //判断当前节点和传入节点的大小
        //添加的节点比当前节点的值更小
        if (node.value < this.value) {
            //如果左节点为空
            if (this.Lnode == null) {
                this.Lnode = node;
            } else {
                this.Lnode.add(node);
            }
        } else {
            //如果右节点为空
            if (this.Rnode == null) {
                this.Rnode = node;
            } else {
                this.Rnode.add(node);
            }
        }
        /**
         * 判断是否是平衡二叉树
         */
        //左子树比右子树高
        if (Lhight()- Rhight()>=2){
            //双旋转
            if (Lnode!=null&&Lnode.Lhight()<Lnode.Rhight()){
                //先左旋转
                Lnode.Lzhuan();
                //再右旋转
                Rzhuan();
            }else {
                //双旋转
                if (Rnode!=null&&Rnode.Lhight()>Rnode.Rhight()) {
                    //先右旋转
                    Rnode.Rzhuan();
                    //再左旋转
                    Lzhuan();
                }else {
                    //右旋转树
                    Rzhuan();
                }
            }
        }
        //右子树比左子树高
        if (Rhight()- Lhight()>=2){
            //左旋转树
            Lzhuan();
        }
    }
    //右旋转树
    private void Rzhuan() {
        //创建新节点
        Node01 newNode = new Node01(value);
        //把当前节点的右节点符给新节点
        newNode.Rnode = Rnode;
        //把当前节点的左节点的右节点给新节点的左子树
        newNode.Lnode = Lnode.Rnode;
        //把当前节点的左节点作为当前节点
        value = Lnode.value;
        //把左子树的左子树给当前节点的左子树
         Lnode = Lnode.Lnode;
         //把新的节点赋给当前节点的右子树
          Rnode = newNode;
    }
    //左旋转树
    private void Lzhuan() {
        //创建新节点
        Node01 newNode = new Node01(value);
        //把当前节点的右节点符给新节点
        newNode.Lnode = Lnode;
        //把当前节点的左节点的右节点给新节点的左子树
        newNode.Rnode = Rnode.Lnode;
        //把当前节点的左节点作为当前节点
        value = Rnode.value;
        //把左子树的左子树给当前节点的左子树
        Rnode = Rnode.Rnode;
        //把新的节点赋给当前节点的右子树
        Lnode = newNode;
    }

    /**
     * 中序遍历
     *
     * @param node
     */
    public void midShow(Node01 node) {
        if (node == null) {
            return;
        }
        midShow(node.Lnode);
        System.out.print(node.value + " ");
        midShow(node.Rnode);
    }

    /**
     * 查找一个节点
     * @param value
     * @return
     */
    public Node01 search(int value) {
        //如果是当前值则返回当前值
        if(this.value == value){
            return this;
        }else if (this.value > value){
            //如果为空则返回
            if (Lnode == null ){
                return null;
            }
            //否则继续调用函数
            return Lnode.search(value);
        }else {
            if (Rnode == null){
                return null;
            }
            return Rnode.search(value);
        }
    }
}

class AvgBinaryTest{
    public static void main(String[] args) {
//        int[] arr = {1,2,3,4,5,6,7,8};
//        int[] arr = {8,9,6,7,5,4};
        int[] arr = {8,9,5,4,6,7};
        //创建一颗二叉树
        AvgBinaryTree  avgBinaryTree = new AvgBinaryTree();
        for (int i : arr) {
            avgBinaryTree.add(new Node01(i));
        }
        //查看高度
        System.out.println("查看高度  "+avgBinaryTree.root.height());
        //左右高度
        System.out.println("右高度 "+avgBinaryTree.root.Rhight()
                          +"\n左高度 "+avgBinaryTree.root.Lhight());
        //查看当前的节点
        System.out.println("查看当前的节点 "+avgBinaryTree.root.value);

    }
}